#pragma 
#include<iostream>
#include<assert.h>
#include<string>
#include<algorithm>
using namespace std;

template<typename T> 
class Heap
{
public:
	Heap()
		:_data(new T[4])
		,_capacity(4)
		,_size(0)
	{}
	~Heap()
	{
		delete[] _data;
		_data = nullptr;
		this->_capacity = this->_size = 0;
	}
	void Push(T x);
	int Top();
	void Pop();
	bool Empty();
private:
	T* _data;
	int _capacity;
	int _size;
};

void AdjustUP(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			swap(a[parent], a[child]);
			parent = child;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		while (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			swap(a[parent], a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

template<typename T>
void Heap<T>::Push(T x)
{
	if (this->_capacity == this->_size)
	{
		this->_capacity *= 2;
		int* tmp = new int[this->_capacity];
		memcpy(tmp, this->_data, sizeof(int) * this->_size);
		delete[] this->_data;
		this->_data = tmp;
	}
	this->_data[this->_size++] = x;
	AdjustUP(this->_data, this->_size - 1);
}

template<typename T>
void Heap<T>::Pop()
{
	assert(this->_size > 0);
	swap(this->_data[0], this->_data[this->_size - 1]);
	this->_size--;
	AdjustDown(this->_data, this->_size, 0);
}

template<typename T>
int Heap<T>::Top()
{
	assert(this->_size > 0);
	return this->_data[0];
}

template<typename T>
bool Heap<T>::Empty()
{
	return this->_size == 0;
}


